package org.aplombh.java.leetcode.all;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class _3无重复字符的最长字串 {
    public static void main(String[] args) {
        System.out.println(new Solution3_2().lengthOfLongestSubstring("abcabcbb"));
    }
}

class Solution3_1 {
    public int lengthOfLongestSubstring(String s) {
        if (s.equals(" "))
            return 1;
        byte[] st = new byte[127];

        int res = 0, max = 0;
        for (int i = 0, j = 0; i < s.length(); i++) {
            int index = s.charAt(i);
            if (st[index] != 1) {
                st[index] = 1;
                res++;
            } else {
                while (st[index] != 0) {
                    int idx = s.charAt(j);
                    st[idx]--;
                    res--;
                    j++;
                }
                i--;
            }
            max = Math.max(max, res);
        }
        return max;
    }
}

class Error3_1 {
    public int lengthOfLongestSubstring(String s) {
        int[] st = new int[127];
        int max = 0;
        for (int i = 0, j = 0; i < s.length(); i++) {
            int index = s.charAt(i);
            // 跳转到哪一位应将这一位之前所有的映射设置为0
            if (st[index] != 0) {
                j = st[index];
                Arrays.fill(st, 0);
            }
            st[index] = i + 1;
            max = Math.max(max, i - j + 1);
        }
        return max;
    }
}

class Solution3_2 {
    public int lengthOfLongestSubstring(String s) {
        int[] st = new int[127];
        int max = 0;
        for (int i = 0, j = 0; i < s.length(); i++) {
            int index = s.charAt(i);
            // 跳转到哪一位应将这一位之前所有的映射设置为0
            if (st[index] != 0) {
                for (int k = j; k < st[index] - 1; k++) {
                    st[s.charAt(k)] = 0;
                }
                j = st[index];
            }
            st[index] = i + 1;
            max = Math.max(max, i - j + 1);
        }
        return max;
    }
}
